package search;

public class FibonacciSearch {
	private static int[] orderArray = new int[]{1,6,12,29,34,55,87,96,124,156,222,256};
	
	private static int[] fibonacciArray = new int[]{0,1,1,2,3,5,8,13,21,34,55,89,144};
	
	public static int search(int key){
		int low = 0,high = orderArray.length-1,mid=0,k=0;
		while(orderArray.length-1 > fibonacciArray[k]-1){
			k++;
		}
		for(int i=orderArray.length-1;i<fibonacciArray[k]-1;i++){
			orderArray[i]=orderArray[orderArray.length-1];
		}
		while(low<=high){
			mid=low+fibonacciArray[k-1]-1;
			if(key<orderArray[mid]){
				high=mid-1;
				k=k-1;
			}else if(key>orderArray[mid]){
				low=mid+1;
				k=k-2;
			}else{
				if(mid<=orderArray.length-1)
					return mid;
				else
					return orderArray.length-1; 
			}
		}
		return -1;
	}
	
	public static void main(String[] args) throws Exception{
		System.out.println("position:"+search(29));
	}
}
